package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-11
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 创建一个基于时间的键值存储类TimeMap，它支持下面两个操作：
 *
 * 1. set(string key, string value, int timestamp)
 *
 * 存储键key、值value，以及给定的时间戳timestamp。
 * 2. get(string key, int timestamp)
 *
 * 返回先前调用set(key, value, timestamp_prev)所存储的值，其中timestamp_prev <= timestamp。
 * 如果有多个这样的值，则返回对应最大的timestamp_prev的那个值。
 * 如果没有值，则返回空字符串（""）。
 */
public class leetcode981 {
    class TimeMap {
        class Node {
            String k, v;
            int t;
            Node (String _k, String _v, int _t) {
                k = _k; v = _v; t = _t;
            }
        }

        Map<String, List<Node>> map = new HashMap<>();
        public void set(String k, String v, int t) {
            List<Node> list = map.getOrDefault(k, new ArrayList<>());
            list.add(new Node(k, v, t));
            map.put(k, list);
        }

        public String get(String k, int t) {
            List<Node> list = map.getOrDefault(k, new ArrayList<>());
            if (list.isEmpty()) return "";
            int n = list.size();
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (list.get(mid).t <= t) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            return list.get(r).t <= t ? list.get(r).v : "";
        }
    }

}
